package DP.Medium;

public class LC0931 {
    public int minFallingPathSum(int[][] matrix) {
        int order = matrix.length; // 阶数
        int[][] dp = new int[order][order];
        for (int i = 0; i < order; i++) dp[0][i] = matrix[0][i];
        for (int i = 1; i < order; i++) {
            for (int j = 0; j < order; j++) {
                int minValue = Integer.MAX_VALUE;
                for (int k = Math.max(j - 1, 0); k <= Math.min(j + 1, order - 1); k++) {
                    minValue = Math.min(minValue, dp[i - 1][k]);
                }
                dp[i][j] = minValue + matrix[i][j];
            }
        }

        int ret = dp[order - 1][0];
        for (int i = 1; i < order; i++) ret = Math.min(ret, dp[order - 1][i]);
        return ret;
    }
}
